using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0257. 二叉树的所有路径")]
    public class No0257_BinaryTreePaths : AbsBaseTestItem
    {
        /*
        给定一个二叉树，返回所有从根节点到叶子节点的路径。
        说明: 叶子节点是指没有子节点的节点。
        */
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(BinaryTreePaths, new TreeNode(1)
            {
                left = new TreeNode(2)
                {
                    right = new TreeNode(5),
                },
                right = new TreeNode(3),
            }, new string[]
            {
                "1->2->5",
                "1->3",
            });
        }

        public IList<string> BinaryTreePaths(TreeNode root)
        {
            List<string> ans = new List<string>();
            void CalcPaths(TreeNode node, string path)
            {
                if (node == null) return;
                path += node.val.ToString();
                if (node.left == null && node.right == null)
                {
                    ans.Add(path);
                    return;
                }
                path += "->";
                CalcPaths(node.left, path);
                CalcPaths(node.right, path);
            }
            CalcPaths(root, "");
            return ans;
        }
    }
}
